1. Field of the Invention
The present invention relates to communication systems, and more particularly, to a method and apparatus for performing diagnostic procedures on queue structures used for storing received data in communication systems.
2. Description of the Related Art
Modern communication systems, such as computer networking systems or communication networks, provide constant transmission of data between end stations and/or intermediate stations such as routers and signal amplifiers. Computer networking, systems, such as packet switched networks (e.g., Ethernet networks), often require transmission of data to a single end station or to multiple end stations within the network. The data originates from a user program and is segmented into multiple data frames, and subsequently transmitted in order to simplify processing and minimize the retransmission time required for error recovery. For example, in a conventional e-mail system, a user may desire to send the same e-mail message to four different users that are connected to the e-mail system. Accordingly, the identical data would be directed to multiple end stations.
Packet switched computer networks typically employ a network switch that receives and forwards data frames to individual and/or multiple end stations. The switch makes forwarding decisions upon receipt of data frames based on information contained in a header of each data frame. For example, if a received data frame is to be transmitted to a number of end stations, the switch must make the forwarding decision to forward the data frame to the ports of the correct end stations. Depending on the specific implementation and/or characteristic of the networking system (i.e., data transfer rate, traffic intensity), buffers must be provided for temporary storage of the data frames, received by the switch, until forwarding decisions can be made. Without the use of buffers, there is a great likelihood that data frames will be lost, hence requiring retransmission and reducing the overall efficiency of the system.
The buffers used by the switch to store the data frames are often implemented as queue structures. There are many types of electronic data systems in which queues are used. These include microprocessors, memory transfer systems, airline telephone reservation systems, and packet switched networks. An example of a queue from everyday life is a customer line, at a bank or an airport ticket counter. In most systems, it is desirable that the queues have low latencies so that processing of an entry is not delayed very long due to delays caused by the queues themselves. A low queue latency means that an entry will flow from the entrance to the queue to the exit of the queue quickly, in comparison to queues with higher latencies. One factor that has a significant impact on the latency of a queue is the length, or capacity, of the queue. The greater the capacity of the queue to store entries, the higher the latency of the queue.
In certain systems, a compromise is typically made between the competing factors of latency and capacity in designing the queue size. For example, the network switch typically receives data frames from multiple ports, and cannot process all of the data frames instantaneously to thereby determine where each should be sent. Hence, a queuing arrangement that queues the received data frames provides the network switch enough time to process the received data frames.
It is often difficult to balance the competing factors of latency and capacity in multiport network switches because of the desire to quickly process received data frames with minimal delay that may be introduced by the queue structure. Regardless of the processing speed of the network switch, it is also important that there is sufficient storage capacity to accommodate large numbers of received data frames. A high storage capacity ensures that received data frames will not be discarded, hence avoiding loss of information even during times of high throughput at the switch.
Further complications arise as a result of the ever-increasing pressure to reduce the size of the chips that embody the device that implements the queue structure, or provide extended functionality in the device. Consequently, the amount of real estate, on the chip, that can be dedicated to the queuing function becomes considerably more expensive. This expense is further increased in devices such as multiport network switches, where each port may be required to have its own queue.
The expense associated with on-chip real estate has traditionally been addressed by providing additional storage area external of the chip (i.e., external memory). The external storage area, however, introduces new problems because access to the xe2x80x9con-chipxe2x80x9d memory is considerably faster than access to the external memory. Consequently, latency is significantly increased.
Accordingly, a principal problem associated with implementing queue structures is the need to efficiently balance competing factors such as latency and storage capacity.
Another problem associated with implementing queue structures is the inability to effectively minimize latency when a large storage capacity is available.
There is a need to provide a queue structure and a method of queuing that will satisfy both competing interests of low latency and high capacity, that queues entries to a system with low latency, yet still retains the capacity to handle relatively large amounts of entries when necessary.
There is also a need for a queue structure that is capable of minimizing latency regardless of the amount of external storage capacity available to store entries.
These and other needs are addressed by the present invention wherein a queue structure includes a queue overflow engine that minimizes latency by selectively utilizing an external memory area, based on a prescribed threshold value.
In accordance with one aspect of the present invention, a queue structure comprises a first queue area for receiving entries, a second queue area for outputting entries input to the first queue area, a queue overflow engine logically coupled to the first queue area and the second queue area, and an overflow storage area operatively coupled to the queue overflow engine. The first queue area and the second queue areas each include an input portion and an output portion. The queue overflow engine functions to transfer entries from the first queue area to the second queue area using either a trickle mode or an overflow mode, based on a prescribed threshold value. Depending on the specific system, the threshold value used by the queue overflow engine may correspond to the number of entries stored in the first queue area, the number of entries stored in the second queue area, or both.
According to one implementation of the present invention, the overflow mode requires that the queue overflow engine perform a first transfer of entries from the output portion of the first queue area to the overflow storage area. Next, the queue overflow engine performs a second transfer wherein the entries currently stored in the overflow storage area are transferred to the second queue area. Furthermore, the trickle mode requires that the queue overflow engine transfer entries directly from the output portion of the of the first queue area into the input portion of the second queue area.
According to another implementation, the queue overflow engine attempts to transfer entries into the second queue area using only the trickle mode, in order to minimize latency resulting from access to the external memory area. The queue overflow engine thus monitors the number of entries currently stored in the first and second queue areas. If the first queue area is empty, then the queue overflow engine refrains from transferring entries from the overflow storage area until a minimum threshold value is reached in the second queue area. If additional entries are input to the first queue area before the minimum threshold value is reached, then entries are transferred to the second queue area directly from the first queue area using the trickle mode.
Hence, the queue overflow engine will only transfer entries from the overflow storage area if there are no entries in the first queue area and the number of entries stored in the second queue area is below the minimum threshold value. Such an arrangement is particularly beneficial when the ordering of entries within the queue does not need to be maintained. One benefit of such an arrangement is that it allows for the storage of large quantities of entries using the external storage area and minimize latency by placing a higher priority on the transfer of entries from the first queue area. In addition, various control factors such as, for example, the size of the overflow storage area and the threshold values may be changed dynamically during operation of the system.
In accordance with another aspect of the invention, a method of queuing entries into a queue structure comprises the steps: receiving entries in a first queue area of the queue structure; comparing the number of entries stored in the first queue area to a prescribed threshold value; and transferring entries from the first queue area into the second queue area using either a trickle mode or an overflow mode, based on the step of comparing. The present invention advantageously allows selective transfer of entries from the first queue area based on predetermined conditions that function to optimize storage capacity while minimizing latency.
According to one embodiment of the invention, the trickle mode requires that entries be transferred directly to the second queue area if there is available capacity in the second queue area in order to minimize latency. If there is no available capacity in the second queue area, then the entries are transferred to an overflow storage area in order to maximize the storage capacity of the queue structure.
Additional advantages and novel features of the present invention will be set forth in part in the description which follows, and in part will become apparent to those skilled in the art upon examination of the following, or may be learned by practice of the invention. The advantages of the invention may be realized and attained by means of the instrumentalities and combinations particularly pointed out in the appended claims.